package com.captain.leetcode.动态规划;

/**
 * @author captain
 * @Des 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 2
 * 输出: 1
 * 解释: 2 = 1 + 1, 1 × 1 = 1。
 * 示例 2:
 * <p>
 * 输入: 10
 * 输出: 36
 * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
 * @Date 2021/7/25 21:46
 */
public class 整数拆分343 {

    public static void main(String[] args) {
        System.out.println(new 整数拆分343().integerBreak(5));
    }

    public int integerBreak(int n) {
        //特殊情况
        if (n == 1) return 1;
        if (n == 2) return 1;
        if (n == 3) return 2;

        //定义dp : dp[i] 时, 拆分i 的最大值
        int[] dp = new int[n + 1];

        //初始化
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            //递推公式
            dp[i] = i;
            for (int j = i - 1; j > 0; j--) {
                dp[i] = Math.max(dp[i], dp[i - j] * j);
            }
        }
        return dp[n];
    }
}
